package fun.coding.leetcode;

public class FactorialTrailingZeroes {

	public static void main(String[] args) {
		FactorialTrailingZeroes ins = new FactorialTrailingZeroes();
		System.out.println(ins.trailingZeroes(30));
		System.out.println(ins.trailingZeroes(1808548329));
	}
	
	// This is log since it keeps dividing 5. this handles the 25 case gracefully. 
	public int trailingZeroes(int n) {
		if (n <= 0) return 0;
		
		int count = 0;
		
		for (int i = n; i > 0; i = i / 5) {
			count += i / 5;
		}
		
		return count;
	}
	
	
	// This is just to count how many 5s in total in O(N)
	public int trailingZeroesLinear(int n) {
		if (n < 5) return 0;
		
		int count = 0;
		
		for (int i = n; i > 0; i--) {
			int res = i;
			while (res % 5 == 0) {
				count++;
				res = res / 5;
			}
		}
		return count;
	}

}
